package main.LeetCode75.Level2;

import java.util.*;

public class Day6_Day10 {
    public static void main(String[] args) {
        System.out.println("**************************Day6**************************");
        System.out.println("Question226：翻转二叉树");
        System.out.println("Question110：平衡二叉树");
        System.out.println("**************************Day7**************************");
        System.out.println("Question543：二叉树的直径");
        System.out.println("Question437：路径总和 III");
        System.out.println("**************************Day8**************************");
        System.out.println("Question33：搜索旋转排序数组");
        System.out.println("Question74：搜索二维矩阵");
        System.out.println("**************************Day9**************************");
        System.out.println("Question108：将有序数组转换为二叉搜索树");
        System.out.println("Question230：二叉搜索树中第K小的元素");
        System.out.println("Question173：二叉搜索树迭代器");
        System.out.println("**************************Day10**************************");
        System.out.println("Question994：腐烂的橘子");
        System.out.println("Question417：太平洋大西洋水流问题");
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Question226{
    public TreeNode invertTree(TreeNode root) {
        reverse(root);
        return root;
    }
    public void reverse(TreeNode node){
        if (node==null) return;
        reverse(node.left);
        reverse(node.right);
        TreeNode temp=node.left;
        node.left=node.right;
        node.right=temp;
    }
}

class Question110{
    public class InfoType{
        public int height;
        public boolean isBalanced;
        public InfoType(int height, boolean isBalanced) {
            this.height = height;
            this.isBalanced = isBalanced;
        }
    }
    public InfoType process(TreeNode root){
        if (root==null) return new InfoType(0,true);
        InfoType leftData=process(root.left);
        InfoType rightData=process(root.right);
        int height=Math.max(leftData.height, rightData.height)+1;
        boolean flag=false;
        if (leftData.isBalanced && rightData.isBalanced && Math.abs(leftData.height- rightData.height)<2) flag=true;
        return new InfoType(height,flag);
    }
    public boolean isBalanced(TreeNode root) {
        return process(root).isBalanced;
    }
}

class Question543{
    public class Info{
        public int maxLength;//记录单侧最长长度
        public int totalLength;//记录节点两侧最远节点距离(即是左右子树单侧最长相加)
        public Info(int max,int total){
            this.maxLength=max;
            this.totalLength=total;
        }
    }
    public Info process(TreeNode root, TreeNode head){
        if (root==null) return new Info(0,0);
        Info left=process(root.left,head);
        Info right=process(root.right,head);
        int totalLength=0;
        int maxLength= left.maxLength > right.maxLength ? left.maxLength+1 : right.maxLength+1;//该节点单边最长距离
        int tempMaxTotal=left.totalLength> right.totalLength? left.totalLength : right.totalLength;//左右子树中最远距离
        if (left.maxLength+ right.maxLength>=tempMaxTotal) totalLength=left.maxLength+ right.maxLength;//该子树最大距离
        else totalLength=tempMaxTotal;
        return new Info(maxLength,totalLength);

    }
    public int diameterOfBinaryTree(TreeNode root) {
        Info result=process(root,root);
        return result.totalLength;
    }
}

class Question437{
    HashMap<Long, Integer> prefix;
    public int pathSum(TreeNode root, int targetSum) {
        prefix = new HashMap<>();
        prefix.put(0L, 1);
        return dfs(root, 0, targetSum);
    }

    public int dfs(TreeNode root, long curr, int targetSum) {
        if (root == null) return 0;
        int ret = 0;
        curr += root.val;
        ret = prefix.getOrDefault(curr - targetSum, 0);
        prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);
        ret += dfs(root.left, curr, targetSum);
        ret += dfs(root.right, curr, targetSum);
        prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);
        return ret;
    }
}

class Question33{
    public int search(int[] nums, int target) {
        int left=0,right= nums.length-1,result=-1;
        while (left<=right){
            int mid=(left+right)/2;
            if (nums[mid]==target) {
                result=mid;
                break;
            }else {
                if (nums[left]<=nums[mid]){//左侧有序
                    if (target>=nums[left]&&target<=nums[mid]) right=mid-1;//target在有序范围内
                    else left=mid+1;//target不在有序范围内
                }else {//右侧有序
                    if (target>=nums[mid]&&target<=nums[right]) left=mid+1;//target在有序范围内
                    else right=mid-1;
                }
            }
        }
        return result;
    }
}

class Question74{
    public boolean searchMatrix(int[][] matrix, int target) {
        int row=-1;
        for (int i=0;i< matrix.length;i++){//确定行
            if (matrix[i][0]<=target) row=i;
        }
        if (row!=-1){
            for (int i=0;i<matrix[0].length;i++){
                if (matrix[row][i]==target) return true;
            }
        }
        return false;
    }
}

class Question108{
    public TreeNode process(int[] nums, int left, int right){
        if (left>right) return null;
        int index=(left+right+1)/2;
        TreeNode curNode=new TreeNode(nums[index]);
        curNode.left=process(nums,left,index-1);
        curNode.right=process(nums,index+1,right);
        return curNode;
    }
    public TreeNode sortedArrayToBST(int[] nums) {
        return process(nums,0, nums.length-1);
    }
}

class Question230{
    public int kthSmallest(TreeNode root, int k) {//非递归中序遍历
        int result=0,count=0;
        TreeNode curNode=root;
        Stack<TreeNode> stack=new Stack<>();
        while (!stack.isEmpty()||curNode!=null){
            if (curNode!=null){
                stack.push(curNode);//入栈
                curNode=curNode.left;//寻找左孩子
            }else {
                TreeNode temp=stack.pop();
                count++;
                if (count==k){
                    result= temp.val;
                    break;
                }
                curNode=temp.right;
            }
        }
        return result;
    }
}

class Question173{
    List<Integer> list;//中序遍历序列
    public Question173(TreeNode root) {
        list=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        while (root!=null||!stack.isEmpty()){
            if (root!=null){
                stack.push(root);
                root=root.left;
            }else {
                root=stack.pop();
                list.add(root.val);
                root=root.right;
            }
        }
    }
    public int next() {
        int next=list.get(0);
        list.remove(0);
        return next;
    }
    public boolean hasNext() {
        return !list.isEmpty();
    }
}

class Question994{
    int[] dr = new int[]{-1, 0, 1, 0};
    int[] dc = new int[]{0, -1, 0, 1};
    public int orangesRotting(int[][] grid) {
        int R = grid.length, C = grid[0].length;
        Queue<Integer> queue = new ArrayDeque<Integer>();
        Map<Integer, Integer> depth = new HashMap<Integer, Integer>();
        for (int r = 0; r < R; ++r) {
            for (int c = 0; c < C; ++c) {
                if (grid[r][c] == 2) {
                    int code = r * C + c;
                    queue.add(code);
                    depth.put(code, 0);
                }
            }
        }
        int ans = 0;
        while (!queue.isEmpty()) {
            int code = queue.remove();
            int r = code / C, c = code % C;
            for (int k = 0; k < 4; ++k) {
                int nr = r + dr[k];
                int nc = c + dc[k];
                if (0 <= nr && nr < R && 0 <= nc && nc < C && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;
                    int ncode = nr * C + nc;
                    queue.add(ncode);
                    depth.put(ncode, depth.get(code) + 1);
                    ans = depth.get(ncode);
                }
            }
        }
        for (int[] row : grid) {
            for (int v : row) {
                if (v == 1) {
                    return -1;
                }
            }
        }
        return ans;
    }
}

class Question417{
    static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int[][] heights;
    int m, n;
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        this.heights = heights;
        this.m = heights.length;
        this.n = heights[0].length;
        boolean[][] pacific = new boolean[m][n];
        boolean[][] atlantic = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            process(i, 0, pacific);
        }
        for (int j = 1; j < n; j++) {
            process(0, j, pacific);
        }
        for (int i = 0; i < m; i++) {
            process(i, n - 1, atlantic);
        }
        for (int j = 0; j < n - 1; j++) {
            process(m - 1, j, atlantic);
        }
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    List<Integer> cell = new ArrayList<Integer>();
                    cell.add(i);
                    cell.add(j);
                    result.add(cell);
                }
            }
        }
        return result;
    }
    public void process(int row, int col, boolean[][] ocean) {
        if (ocean[row][col]) return;
        ocean[row][col] = true;
        for (int[] dir : dirs) {
            int newRow = row + dir[0], newCol = col + dir[1];
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && heights[newRow][newCol] >= heights[row][col]) {
                process(newRow, newCol, ocean);
            }
        }
    }
}